1817B - Fish Graph - CodeForces Solution

#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <functional>
#include <complex>
#include <random>

using namespace std;
 
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ld long double
 
const ll maxn = 2e3 + 1, maxm = 1e3 + 1;
const ll mod = 1e9 + 7, cmod = 998244353, inf = 1e9, blcok = 400, p2 = 31;
const ld eps = 1e-9;

int t, timer;
int n, m;
int dp[maxn], tin[maxn], used[maxn], color[maxn], colc[maxn], par[maxn];
vector<int> g[maxn], g2[maxn];
int foo[maxn], bar[maxn];
map<pair<int, int>, int> reb;
map<int, int> fix;
vector<int> ans;
void dfs(int v, int p){
    used[v] = 1;
    tin[v] = ++timer;
    dp[v] = tin[v];
    for (auto to : g[v]){
        if (to != p){
            if (used[to]){
                dp[v] = min(dp[v], tin[to]);
            }
            else{
                dfs(to, v);
                dp[v] = min(dp[v], dp[to]);
                if (dp[to] > tin[v]){
                    reb[mp(v, to)] = 1;
                    reb[mp(to, v)] = 1;
                }
            }
        }
    }
}
void dfs2(int v, int c){
    used[v] = 1;
    color[v] = c;
    colc[c] += 1;
    for (auto to : g2[v]){
        if (used[to] == 0){
            dfs2(to, c);
        }
    }
}
void dfs3(int v, int p, int root){
    if ((int)ans.size() > 0){
        return;
    }
    used[v] = 1;
    for (auto to : g[v]){
        if ((int)ans.size() > 0){
            return;
        }
        if (color[to] != color[root] || fix[to] || to == p){
            continue;
        }
        if (used[to] == 0){
            par[to] = v;
            dfs3(to, v, root);
        }
        else{
            if (to == root){
                while (v != to){
                    ans.pb(v);
                    v = par[v];
                }
                ans.pb(v);
                return;
            }
        }
    }
}
int main(){
    cin >> t;
   // cout << t << '\n';
    while (t--){
        cin >> n >> m;
        for (int i = 1; i <= m; ++i){
            cin >> foo[i] >> bar[i];
            int u = foo[i], v = bar[i];
            g[u].pb(v);
            g[v].pb(u);
        }
        timer = 0;
        for (int i = 1; i <= n; ++i){
            g2[i].clear();
            colc[i] = 0;
            color[i] = 0;
            used[i] = 0;
            dp[i] = 0;
            tin[i] = 0;
        }
        fix.clear();
        ans.clear();
        reb.clear();
        //5 7
        //3 5
        //5 2
        //2 4
        //2 1
        //4 3
        //2 3
        //1 4
        for (int i = 1; i <= n; ++i){
            if (used[i] == 0){
                dfs(i, 0);
            }
        }
        for (int i = 1; i <= m; ++i){
            int u = foo[i], v = bar[i];
            if (reb[mp(u, v)] == 0){
                g2[u].pb(v);
                g2[v].pb(u);
            }
        }
        for (int i = 1; i <= n; ++i){
            used[i] = 0;
        }
        int col = 0;
        for (int i = 1; i <= n; ++i){
            if (used[i] == 0){
                dfs2(i, ++col);
            }
        }
        for (int i = 1; i <= n; ++i){
            used[i] = 0;
        }
        vector<pair<int, int>> answ;
        for (int i = 1; i <= n; ++i){
            if (colc[color[i]] > 1 && (int)g[i].size() >= 4){
                for (int j = 0; j < 4 && (int)answ.size() == 0; ++j){
                    for (int k = j + 1; k < 4 && (int)answ.size() == 0; ++k){
                        for (int is = 1; is <= n; ++is){
                            used[is] = 0;
                        }
                        int u = g[i][j];
                        int v = g[i][k];
                        fix[u] = 1;
                        fix[v] = 1;
                        dfs3(i, -1, i);
                        if ((int)ans.size() > 0){
                            int nn = (int)ans.size();
                            for (int is = 0; is < nn; ++is){
                                answ.pb(mp(ans[is], ans[(is + 1) % nn]));
                            }
                            answ.pb(mp(i, u));
                            answ.pb(mp(i, v));
                        }
                        fix[u] = 0;
                        fix[v] = 0;
                    }
                }
            }
        }
        if ((int)answ.size() > 0){
            cout << "YES\n";
            cout << (int)answ.size() << '\n';
            for (auto it : answ){
                cout << it.f << " " << it.s << '\n';
            }
        }
        else{
            cout << "NO\n";
        }
        timer = 0;
        for (int i = 1; i <= n; ++i){
            g[i].clear();
            g2[i].clear();
            colc[i] = 0;
            color[i] = 0;
            used[i] = 0;
        }
        fix.clear();
        ans.clear();
        reb.clear();
    }
}
/*
*/